package com.cn.algorithm02.class15;

import java.util.Comparator;
import java.util.PriorityQueue;

/***
 * @author: hels
 * @description: 项目最大获利问题：
 * 可以做的项目为k个，初始资金M, 正整数数组cost为每个项目的花费，数组profits为对应项目的纯利润收益
 * 两个数组长度一致
 * 问最大收益方案
 **/
public class C03_IPO {
    public static void main(String[] args) {
        // m = 2    return 2;
        // m = 5    return 21;
        int k = 3, m = 2;
        int[] costs =   {4, 5, 3, 7, 8, 9};
        int[] profits = {2, 4, 5, 2, 7, 2};
        System.out.println(mostProfit(k, m, costs, profits));

    }

    /**
     * 通过贪心算法处理
     * @param k
     * @param m
     * @param costs
     * @param profits
     * @return
     */
    public static int mostProfit(int k, int m, int[] costs, int[] profits) {
        // 小根堆
        Comparator<Program> minComp = new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o1.cost - o2.cost;
            }
        };

        // 大根堆
        PriorityQueue<Program> minQueue = new PriorityQueue<>(minComp);
        Comparator<Program> maxComp = new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o2.profit - o1.profit;
            }
        };
        PriorityQueue<Program> maxQueue = new PriorityQueue<>(maxComp);

        for (int i = 0; i < costs.length; i++) {
            minQueue.add(new Program(costs[i], profits[i]));
        }

        int curMoney = m;
        for (int j = 0; j < k; j++) {
            while (!minQueue.isEmpty() && minQueue.peek().cost < curMoney) {
                maxQueue.add(minQueue.poll());
            }

            // 收益大根堆中为空，则直接返回收益
            if (maxQueue.isEmpty()) {
                return curMoney;
            }

            curMoney += maxQueue.poll().profit;
        }

        return curMoney;
    }

    public static class Program {
        public int cost;
        public int profit;

        public Program(int c, int p) {
            cost = c;
            profit = p;
        }
    }
}
